package tree.leetcode_105_medium;

import java.util.HashMap;
import java.util.Map;

public class BuildTree2 {
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i],i);
        }
        return dfs(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }
    public TreeNode dfs(int[] preorder, int preLeft, int preRight, int inLeft, int inRight){
        if(preLeft > preRight || inLeft > inRight){
            return null;
        }
        int rootVal = preorder[preLeft];
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = map.get(rootVal);
        root.left = dfs(preorder, preLeft + 1, preLeft + rootIndex - inLeft, inLeft , rootIndex - 1);
        root.right = dfs(preorder, preLeft + rootIndex - inLeft + 1, preRight, rootIndex + 1, inRight);
        return root;
    }
}
